package hashTable;

import java.util.*;

public class hashTableTest2 {
    /**
     * 1. 两数之和 -easy
     * @param nums
     * @param target
     * @return
     * // 哈希映射
     */
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        if(nums == null || nums.length < 2) {
            return res;
        }
        for(int i = 0; i < nums.length; i++) {
            int count = map.getOrDefault(target - nums[i], -1);
            if(count != -1) {
                res[0] = count;
                res[1] = i;
                return res;
            } else {
                map.put(nums[i], i);
            }
        }
        return res;

    }


    /**
     * 454. 四数相加 II -medium
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */

    //相当于简化为两数之和
    //而且这道题运行符合结果的元组重复
    //比如：        int[] nums1 = {1,1,1};
    //        int[] nums2 = {1,1,1};
    //        int[] nums3 = {-1,-1,-1};
    //        int[] nums4 = {-1,-1,-1};
    //结果就有81种
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        //先讲a+b的和和出现次数存入map
        for(int i:nums1){
            for(int j:nums2){
                int sum=i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        //再在c+d中找0-c-d;
        for(int i:nums3){
            for(int j:nums4){
                res+=map.getOrDefault(0-i-j,0);
            }
        }
        return res;
    }


    /**
     * 383. 赎金信 -easy
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        //统计 magazine中每个字符出现的次数
        for (int i = 0; i < magazine.length(); i++) {
            count[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            count[ransomNote.charAt(i) - 'a']--; //减去ransomNote字符串中每个字符出现的次数
            if (count[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;

    }


    /**
     * 15. 三数之和 -medium
     * @param nums
     * @return
     */

    //1.排序+双指针，定一移二，重点在于去重
    //一个i 循环，固定一个数，然后双指针left right双向移动
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //1.先排序
        Arrays.sort(nums);
        if (nums == null || nums.length < 3) {
            return res;
        }
        int left,right;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return res;
            }
            //但这里思考一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。
            //[-1,-1,2]
            //nums[i] == nums[i-1]时，跳过，避免重复
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            left = i+1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    //存储这次结果
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //要先存结果，再移动指针
                    //先去重
                    while (left < right && nums[left + 1] == nums[left]) {
                        //跳过重复 -left去重
                        left++;
                    }
                    while (left < right && nums[right - 1] == nums[right]) {
                        //跳过重复 -right去重
                        right--;
                    }
                    //这一步千万别忘了,left,right移动下一位置
                    left++;
                    right--;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    //如果大于0，则调小一点
                    right--;
                } else {
                    //如果小于0，则调大一点
                    left++;
                }
            }
        }
        return res;
    }


    /**
     * 18. 四数之和 -medium -区别于454. 四数相加 II
     * 该题是要符合结果的不重复四元组
     * //思路是和15. 三数之和的思路一样，只是多加了一层循环，多加了一层去重
     * //还有target不是固定的0，而是任意值 --所以去重逻辑有所不同
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int k = 0; k < nums.length; k++) {
            //剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break;
            }
            //对k去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                //二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                //对i去重 --二级去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long sum =(long) nums[k] + nums[i] + nums[left] + nums[right];
                    if(sum > target) {
                        right--;
                    } else if(sum < target) {
                        left++;
                    } else {
                        //==target
                        res.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        //还是老问题 去重后别忘了移动指针 -不然这个while 循环会死循环
                        left++;
                        right--;
                    }
                }
            }

        }
        return res;

    }

    public static void main(String[] args) {
        hashTableTest2 test = new hashTableTest2();
        int[] nums1 = {1,1,1};
        int[] nums2 = {1,1,1};
        int[] nums3 = {-1,-1,-1};
        int[] nums4 = {-1,-1,-1};
        System.out.println(test.fourSumCount(nums1, nums2, nums3, nums4));
    }

}
